#include <stdio.h>
#include <string.h>

// 计算最长前缀后缀数组(LPS)
void computeLPS(char* pattern, int m, int* lps) {
    int length = 0;  // 当前最长前缀后缀的长度
    lps[0] = 0;     // 第一个字符的LPS值为0
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                // 回溯到上一个可能的匹配位置
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// KMP搜索算法
int kmpSearch(char* text, char* pattern) {
    int n = strlen(text);    // 开锁字符序列长度
    int m = strlen(pattern); // 密码长度

    if (m == 0) return 0;    // 密码为空时返回失败

    int* lps = (int*)malloc(m * sizeof(int));
    computeLPS(pattern, m, lps);

    int i = 0;  // text的索引
    int j = 0;  // pattern的索引

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            // 找到匹配，返回成功
            free(lps);
            return 1;
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                // 利用LPS数组回溯
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    free(lps);
    return 0;  // 未找到匹配，返回失败
}

int main() {
    char password[100];    // 预设密码
    char sequence[1000];   // 开锁字符序列

    printf("电子密码锁验证系统\n");
    printf("-------------------\n");

    printf("请输入预设密码: ");
    fgets(password, sizeof(password), stdin);
    // 移除fgets带来的换行符
    password[strcspn(password, "\n")] = '\0';

    printf("请输入开锁字符序列: ");
    fgets(sequence, sizeof(sequence), stdin);
    // 移除fgets带来的换行符
    sequence[strcspn(sequence, "\n")] = '\0';

    if (strlen(password) == 0) {
        printf("错误：预设密码不能为空！\n");
        return 1;
    }

    // 执行KMP搜索
    if (kmpSearch(sequence, password)) {
        printf("验证成功，密码正确，可以开锁！\n");
    } else {
        printf("验证失败，字符序列中不包含预设密码，无法开锁！\n");
    }

    return 0;
}
